FIG. 1A is a schematic diagram illustrating a hierarchy of network routers. Edge routers 11-13 and 21-23 at the edge of the network 10 communicate directly with clients or through Internet service providers 15-16 and 25. Core routers 17-20 near the core 14 of network 10 communicate directly with other routers, but typically not so much with end clients. This structure is hierarchical in the sense that one core router might fan out very high speed links to multiple edge routers, which might in turn fan out to multiple corporate routers or service providers.
A router builds a route map of the Internet typically consisting of a table of 32-bit IP addresses for IPV4 (Internet Protocol Version 4) to the egress (output) port of the router. When a router receives a packet for a certain IP address, the destination IP address in the packet header is looked up in the table to select one out of many egress ports to send the packet. To build this routing table, a router establishes relationships called adjacencies with other routers using special protocols. Protocols are often layered, i.e., one protocol is built on top of another protocol.
FIG. 1B is a block diagram illustrating conventional protocol headers in a data packet. Looking at the bytes in a packet 125, there is typically an Ethernet header 121, which is the lowest layer specifying how to transfer the packet physically. Then there are typically an Internet protocol (IP) header 122 and a transmission control protocol (TCP) header 123. Finally there is typically a border gateway protocol (BGP) header 124.
FIG. 1C is a diagram illustrating how routers typically communicate with one another. Routers communicate with one another about routes using BGP protocol 31, which is built on top of TCP protocol 32, OSPF protocol 33 and various other layered protocols 34-35 as depicted in FIG. 1C. The BGP protocol of Router 40 communicates with the BGP protocols of other routers, e.g., Router 41. and Router 42, through datalinks 101 and 102. Thus all of the routers in the network collaborate together to construct the same route map 45 of the Internet as shown within all peer routers 40-42.
BGP is built on top of TCP, which is a connection oriented protocol, similar to a telephone. After a connection period at the beginning of a call, an end party once connected does not change, unlike a datagram service protocol (DSP), in which each packet flows totally independent of the packets before it. Bytes can flow back and forth bidirectionally from one TCP engine to another. Because BGP is built on top of TCP, it inherits these connection oriented characteristics. BGP establishes a connection between peer routers, like a phone call, such that peer routers send messages back and forth bidirectionally, analogous to having open phone lines between one another. BGP is a routing protocol used to construct the network route maps. The program that uses BGP is the routing software, which constructs the actual routing table.
A router needs to know if a peer router is alive, and vice-versa. All routers need to know that, and they do so by sending periodic BGP keep-alive packets across datalinks, for example datalinks 101 and 102, to make sure that the peer router answers. A very large core router typically has on the order of a thousand peer router datalinks. Each peer router needs a keep-alive packet sent to it on the order of every ten seconds. That means that there will be on the order of a hundred keep-alive packets per second transmitted by a large core router. Referring to FIG. 1C, ingress ports 103 and egress ports 104, distributed among multiple router line shelves, communicate with each of the peer routers.
A dynamic routing protocol (DRP) is basically an application that runs on this operating system Master Control Processor (MCP) and is responsible for building route maps, communicating with the peer routers, and processing keep-alive packets. There is essentially one active MCP controlling an entire router system, which communicates through internal control networks with all of the line shelves that contain the line cards that communicate with ingress and egress ports and with other routers. The reason for a single active MCP is to build a single integrated centralized routing table that encompasses the whole Internet. This routing table is distributed to packet forwarding engines in the router line shelves, which perform the actual packet processing. This results in a distributed system containing many CPUs for scalability and reliability purposes, all coordinated by a single MCP.
A problem is that the DRP application does not run in real time, yet all of the keep-alive packets need to be processed in real time, because aspects of sending keep-alive packets have hard time limits. The dynamic routing protocols run in user space on top of a non-real time Unix-based OS, which is chosen for other reasons. Therefore, it is desirable to develop a system and method of efficient real time router keep-alive control that does not require the very large DRP application, containing more than 300,000 lines of code, to run in its entirety as a real time application. It is further desirable to develop such a system with a simple user interface and with minimal modification of existing source code or system utilities.